package 回溯;

import java.util.ArrayList;
import java.util.List;

public class q17电话号码的字母组合 {
    class Solution {
        List<String> list = new ArrayList<>();

        public List<String> letterCombinations(String digits) {

            if (digits == null || digits.length() == 0) {
                return list;
            }

            String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  // 对应键盘字母

            backtrack(digits, numString, 0);


            return list;

        }
        StringBuilder temp = new StringBuilder();

        void backtrack(String digits, String[] numString, int index) {

            if (index == digits.length()) {
                list.add(temp.toString());
                return;
            }
            String str = numString[digits.charAt(index) - '0']; // digits.charAt(index) - '0' 将char转为int ,原理是符 '0' 到 '9' 在 Unicode 编码中是连续的
            for (int i = 0; i < str.length(); i++) {
                temp.append(str.charAt(i));
                backtrack(digits, numString, index + 1);
                temp.deleteCharAt(temp.length() - 1);
            }
        }
    }
}
